/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-04-09
 * Time: 23:21
 */
//152.乘积最大子数组
class Solution3 {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        //1.创建dp表
        //f[i]以i结尾的最大子数组乘积
        //g[i]以i结尾的最小子数组乘积
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        //2.初始化(不影响后面的值,1*nums[i]仍然是num[i])
        f[0] = 1; g[0] = 1;
        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            int x = nums[i-1],y = f[i-1]*nums[i-1],z = g[i-1]*nums[i-1];
            f[i] = Math.max(x,Math.max(y,z));
            g[i] = Math.min(x,Math.min(y,z));
            ret = Math.max(f[i],ret);
        }
        return ret;
    }
}
